class Solution
{
public:
    int minHeightShelves(vector<vector<int>> &books, int shelfWidth)
    {
        int n = books.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        dp[1] = books[0][1];
        for (int i = 1; i < n; ++i)
        {
            int layerMaxHeight = books[i][1];
            int layerWidth = books[i][0];
            dp[i + 1] = dp[i] + layerMaxHeight;
            for (int j = i - 1; j >= 0; --j)
            {
                layerWidth += books[j][0];
                if (layerWidth > shelfWidth)
                {
                    break;
                }
                layerMaxHeight = max(layerMaxHeight, books[j][1]);
                dp[i + 1] = min(dp[i + 1], dp[j] + layerMaxHeight);
            }
        }
        return dp[n];
    }
};